package summary;

import java.util.*;

/**
 * @Author: 海琳琦
 * @Date: 2022/7/22 15:22
 * https://leetcode.cn/problems/shortest-path-visiting-all-nodes/
 */
public class Title847 {

    class State{
        int id;

        //节点的状态
        int mask;

        int dist;

        public State(int id, int mask, int dist) {
            this.id = id;
            this.mask = mask;
            this.dist = dist;
        }
    }

    public int shortestPathLength(int[][] graph) {
        int n = graph.length;
        //存放每个节点，对应的状态，每个状态只能经过一次（经过多次无作用）
//        Map<Integer, Set<String>> visited = new HashMap<>();
        int[][] visited = new int[n][1 << n];
        Queue<State> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            queue.offer(new State(i, 1 << i, 0));
//            visited.computeIfAbsent(i, g -> new HashSet<>()).add(1 << i);
            visited[i][1 << i] = 1;
        }
        while (!queue.isEmpty()) {
            State state = queue.poll();
            int curId = state.id;
            int curMask = state.mask;
            int curDist = state.dist;
            if (curMask == (1 << n) - 1) {
                return curDist;
            }
            //邻接节点
            for (int nextId : graph[curId]) {
                int nextMask = curMask | (1 << nextId);
                if (visited[nextId][nextMask] != 1) {
                    visited[nextId][nextMask] = 1;
                    queue.offer(new State(nextId, nextMask, curDist + 1));
                }
//                if (!visited.get(nextId).contains(nextMask)) {
//                    visited.computeIfAbsent(nextId, g -> new HashSet<>()).add(nextMask);
//                    queue.offer(new State(nextId, nextMask, curDist + 1));
//                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(1<<2);
    }
}
